"""
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

718. 最长重复子数组
中等
相关标签
相关企业
提示
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

 

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
 

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

"""

from typing import List


class Solution:
    """
    典型的二维动态规划
    假定用dp[i1][i2]表示nums1[:i1]和nums2[:i2]的最长公共子数组
    此题与s1143的思路看似一模一样，实则有个术语上的区别：
    子数组要求是连续的
    子序列并不要求连续

    dp[0][?]=0
    dp[?][0]=0
    if nums1[i1]!=nums2[i2] then dp[i1+1][i2+1]=0
    else dp[i1+1][i2+1]=dp[i1][i2]+1

    同时维护一个global_max

    """
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        dp=[[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
        global_max=0
        for (i1,n1) in enumerate(nums1):
            for (i2,n2) in enumerate(nums2):
                if n1==n2:
                    dp[i1+1][i2+1]=dp[i1][i2]+1
                    global_max=max(global_max,dp[i1+1][i2+1])

        return global_max

if __name__=='__main__':
    nums1, nums2 = [0,1,1,1,1],[1,0,1,0,1]

    sol=Solution()
    res=sol.findLength(nums1,nums2)
    print(res)

    pass